( , j)

g

gap is allowed to be inserted for the cell (i, j). For instance, if

i^th and iെ1^th residues of sequence x are aligned with gaps, a

move is from cell (i – 2, j) to cell (i, j).

ign the j^th residue of sequence y with a gap, no residue from

x is picked up. This means that the i^th residue of sequence x is

with other residue of sequence y in previous alignment. This is

e horizontal move, i.e., moving from the cell (i, jെ1) on the left

he cell (i, j). Similar as the vertical move mentioned above, the

l move can be done across more than one cell. For instance, if

j^th and jെ1^th residues of sequence y are aligned with gaps, a

l move is from the cell (i, j െ 2) to the cell (i, j).

The initialisation of the dynamic programming table for using the Smith-

algorithm. The left panel is used for calculating the alignment scores cell by cell

ht panel is used for recording the moving directions for cells.

0

1

2

3

4

5

6

1

2

3

4

5

6

A

A

C

U

C

U

A

A

C

U

C

C

0

0

0

0

0

0

0

0

0

0

0

0

0

0

he initialisation

h-Waterman algorithm also needs an initialisation stage. Suppose

th-Waterman algorithm is used to align two sequences,

UGA and y=AACUCC. Table 7.12 shows a dynamic programming

the Smith-Waterman algorithm and how the initialisation was

his table for aligning these two sequences. In the initialisation

ap penalty was filled in for the cells in the initial row and initial

This is similar to the Sellers algorithm. Because a gap penalty

the Smith-Waterman algorithm was negative, it was capped to